Visión Computacional

1 Contenido de la clase

Árbol de recubrimiento y el algoritmo voraz de Kruskal [00:00-09:11]

La clase comienza (tras un fragmento de video con "¡Suscríbete al canal!") retomando un tema de árboles en grafos con pesos. Para facilitar el análisis se supone que los pesos de todas las aristas son distintos [01:22-01:26]. El algoritmo estudiado es el algoritmo de Kruskal: ordenar las aristas por peso creciente e ir agregando las que no forman un ciclo hasta completar el árbol [02:02-02:24]. El objetivo de esta parte es probar que el algoritmo efectivamente genera un árbol de recubrimiento (un árbol que toca todos los vértices sin ciclos) [02:02-02:24, 06:32-09:11].

Cómo funciona el algoritmo y cuántas aristas toma [02:35-06:12]

Durante la ejecución hay un diálogo con la clase: se van tomando las aristas de menor peso (se comentan pesos como 2, 3, 3.5 y 4) y se comprueba cuáles "entran" y cuáles no (las que cerrarían un ciclo se dejan de lado) [02:35-03:23]. Se discute qué pasa si se cambia el peso de una arista [03:53-04:03]. La cuenta clave: si el grafo tiene N vértices, el árbol de recubrimiento usa exactamente N − 1 aristas; por eso el algoritmo se detiene al completarlas (el árbol del ejemplo se colorea de azul) [05:07-05:30, 06:04-06:12, 42:40-42:58]. [parte no entendida — el detalle de la demostración formal no se distingue en la grabación].

Discusión y cierre de la demostración [06:32-09:11]

Se plantean preguntas retóricas para convencerse de que el algoritmo "no se equivoca": aunque aparezca una arista tentadora de menor peso que no se puede tomar porque formaría ciclo, al final el algoritmo produce un árbol de recubrimiento [06:32-07:51]. El profesor lo presenta como el argumento de la prueba de que el algoritmo siempre da un árbol [09:01-09:11]. [parte no entendida — varias frases intermedias del razonamiento se pierden por el ruido].

Grafos planos: vértices, aristas y la cota 3n − 6 [20:20-29:00, 42:25-49:00]

Se pasa a trabajar con una gráfica plana (un grafo que se puede dibujar sin cruzar aristas) [20:20-20:28, 48:38-48:40]. El profesor explora cómo contar aristas y caras, revisando región por región si algo "toca" o no [22:24-23:18, 24:19-24:51]. La fórmula que aparece repetida es la cota máxima de aristas de un grafo plano: con n vértices, a lo sumo hay 3n − 6 aristas (la transcripción la deforma como "3 veces en los lápices, menos una cara de la nota", "el 3 de menos 6" o "los tres nes") [43:22-43:43, 44:46, 48:40-48:42]. También se cuenta el número de aristas de un árbol (n − 1) y se comenta que no siempre se alcanza la cota [43:29-43:46]. [parte no entendida — el ejemplo numérico completo desarrollado en la pizarra].

m ≤ 3n − 6 [43:22-43:43]

Triangulación de las caras [42:09-42:25]

Dentro de los grafos planos aparece la triangulación: se pregunta cuántas aristas faltan para triangular las caras del grafo (agregar diagonales para que todas las regiones queden como triángulos) [42:09-42:25]. Es el paso que conecta con la cota 3n − 6: un grafo plano maximal está triangulado y tiene exactamente 3n − 6 aristas. [parte no entendida — el desarrollo con el grafo concreto de 11 vértices no se distingue bien].

Coloreo de grafos [63:23-81:26]

La parte final estudia el coloreo de grafos: la pregunta es "¿qué podemos hacer sobre un grafo?" y la respuesta es colorearlo con diferentes colores [64:11-64:13]. La regla del coloreo válido: los vértices adyacentes (vecinos) no pueden compartir color [64:13-64:17]. Se aplica una estrategia voraz: se visitan los vértices (por ejemplo empezando por los de mayor grado), se mira qué colores ya usan sus vecinos y se asigna el primer color libre [65:58-66:17, 80:00-80:26]. En el ejemplo se terminan usando 5 colores (la transcripción dice "5 dólares" y "voy a utilizar 5") [64:47-64:51, 66:06-66:08, 80:20-80:22], asignando números 1, 2, 3, 4, 5 según los vecinos ya coloreados [66:18-66:46]. [parte no entendida — la explicación de por qué no se puede usar menos colores en ese grafo concreto].

Cierre y ruido de videos [81:26-84:00]

La clase termina con el comentario "lo vemos en el próximo video" y fragmentos de audio de videos (incluido un acertijo lógico con los números 98, 99 y 100 y "mentirosos" que no se entiende) [81:26-84:00]. [parte no entendida — el audio final es solo ruido de videos].

2 Puntos destacados / Lo que hay que saber

3 Actividades y tareas pendientes

El profesor comenta que tiene que decidir qué ejercicio dejar para la próxima ocasión y señala que algunos casos son más fáciles que otros [27:55-28:40].

*[parte no entendida — no queda clara en la grabación la fecha de entrega ni el ejercicio concreto]

4 Dudas que podrían examinar

5 Sitios o recursos para visitar

El profesor no mencionó libros, páginas o plataformas específicas en la grabación; estos recursos son útiles para profundizar:

6 Glosario de términos

• Grafo: conjunto de vértices (nodos) unidos por aristas.
• Peso de una arista: valor asociado a la arista (costo, distancia, etc.).
• Ciclo: recorrido cerrado que vuelve a un vértice sin repetir aristas; un árbol no tiene ciclos.
• Árbol de recubrimiento (generador): árbol que conecta todos los vértices; con N vértices tiene N − 1 aristas.
• Algoritmo de Kruskal: algoritmo voraz que construye el árbol de recubrimiento mínimo agregando aristas por peso creciente si no forman ciclo.
• Grafo plano: grafo que puede dibujarse en el plano sin que sus aristas se crucen.
• Cara (región) de un grafo plano: zona en que el dibujo divide al plano; la cota 3n − 6 se obtiene contando caras con la fórmula de Euler.
• Grafo plano maximal (triangulado): grafo plano en el que ya no se puede agregar otra arista; tiene exactamente 3n − 6 aristas y todas sus caras son triángulos.
• Triangulación: agregar aristas (diagonales) a las caras de un grafo plano para que todas queden triangulares.
• Coloreo de grafos: asignar colores a los vértices tal que los vértices adyacentes no compartan color.
• Coloreo voraz (greedy): asignar a cada vértice el primer color libre según los colores de sus vecinos, visitándolos en algún orden (p. ej. por grado).
• Grado de un vértice: número de aristas (o vecinos) que inciden en él.

7 Mapa mental textual

• Árboles de recubrimiento, grafos planos y coloreo · Clase 9
  • Árbol de recubrimiento (Kruskal)
    • Supuesto: pesos de las aristas todos distintos
    • Algoritmo voraz: aristas por peso creciente, sin ciclos, N − 1 aristas
    • Prueba: siempre produce un árbol de recubrimiento
  • Grafos planos
    • Dibujables sin cruces
    • Cota de aristas: m ≤ 3n − 6
    • Triangulación de las caras (grafo maximal)
  • Coloreo de grafos
    • Vértices adyacentes con colores distintos
    • Estrategia voraz: primer color libre según vecinos
    • Ejemplo con 5 colores
  • Cierre
    • Discusión de ejercicios para la próxima
    • Audio final con ruido de videos (acertijo ininteligible)